package algorithm_primary.studyMySelf.sort;

import java.util.Arrays;

/**
 * @author 衡孟浩
 * @date 2023/5/17 21:08
 */
public class 插入排序 {
    public static void main(String[] args) {
        int[] arr = {1,2,1,34,1,23,342,1,42,1,2,3,1,21,1,21,23};
        insertSort(arr);
        System.out.println(Arrays.toString(arr));
    }

    /**
     * 插入排序
     * @param arr
     */
    private static void insertSort(int[] arr) {
         if (arr == null || arr.length < 2){
             return;
         }
         // 先让  0-1 上边有序
        //  再让 0-2上有序   如果第二个比第一个小那么就交换位置直到前一个比后一个小为止
        for (int i = 1; i < arr.length; i++) {
            // 0-1
            // 0-2
            // 0-3
            int endIndex = i;
            while (endIndex > 0 && (arr[endIndex - 1] > arr[endIndex])){
                int temp = arr[endIndex - 1];
                arr[endIndex - 1] = arr[endIndex];
                arr[endIndex] = temp;
                endIndex -- ;
            }
        }
    }
}
